UVa/12320 - Flight Control/12320.3.cpp

   1 // Ternary search. TLE.
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 template <class T> string toStr(const T &x) { stringstream s; s << x; return s.str(); }
  25 template <class T> int toInt(const T &x) { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl
  30
  31 const double EPS = 1e-10;
  32
  33 int cmp(double x, double y = 0, double tol = EPS){
  34     return( x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 struct point {
  38     double x, y, z;
  39     point(){} point(double x, double y, double z) : x(x), y(y), z(z) {}
  40 };
  41
  42 int R[2], V[2];
  43 vector< point > P[2];
  44
  45 inline double dist(const point &a, const point &b) {
  46     double dx = b.x - a.x, dy = b.y - a.y, dz = b.z - a.z;
  47     return sqrt(dx * dx + dy * dy + dz * dz);
  48 }
  49
  50 bool equalWithTolerance(double a, double b) {
  51     return cmp(a, b) == 0;
  52 }
  53
  54 point positionAt(int p, double t) {
  55     double d = V[p] * t, s = 0.0;
  56     for (int i = 0; i < P[p].size() - 1; ++i) {
  57         double distance = dist(P[p][i], P[p][i+1]);
  58         if (cmp(s + distance, d) < 0) {
  59             s += distance;
  60         } else {
  61             //assert(cmp(distance, 0) > 0);
  62             point ans = P[p][i];
  63             double dx = P[p][i+1].x - P[p][i].x;
  64             double dy = P[p][i+1].y - P[p][i].y;
  65             double dz = P[p][i+1].z - P[p][i].z;
  66             ans.x += (d - s) * dx / distance;
  67             ans.y += (d - s) * dy / distance;
  68             ans.z += (d - s) * dz / distance;
  69
  70             assert(cmp(s + dist(P[p][i], ans), d) == 0);
  71             return ans;
  72         }
  73     }
  74     assert(false);
  75 }
  76
  77 double distanceAtTime(double t) {
  78     point p0 = positionAt(0, t);
  79     point p1 = positionAt(1, t);
  80     return dist(p0, p1);
  81 }
  82
  83 double touchAtTime(double t) {
  84     return cmp(distanceAtTime(t), 0.0 + R[0] + R[1]) <= 0;
  85 }
  86
  87 double findClosestTime(double left, double right) {
  88     // double bestTime = -1, bestDistance = 1e200;
  89     // for (double t = left; t <= right; t += 0.5) {
  90     //     double d = distanceAtTime(t);
  91     //     printf("At time %lf, distance is %lf\n", t, d);
  92     //     if (cmp(d, bestDistance) < 0) {
  93     //         bestDistance = d;
  94     //         bestTime = t;
  95     //     }
  96     // }
  97
  98     for (int i = 0; i < 100; ++i) {
  99         double t1 = (2 * left + right) / 3;
 100         double t2 = (2 * right + left) / 3;
 101         double d1 = distanceAtTime(t1);
 102         double d2 = distanceAtTime(t2);
 103         if (d1 > d2) {
 104             left = t1;
 105         } else {
 106             right = t2;
 107         }
 108     }
 109     //double ans = (left + right) / 2;
 110     double ans = left;
 111     //printf("Best is at time %lf, where distance is %lf\n", ans, distanceAtTime(ans));
 112     return ans;
 113 }
 114
 115 int main(){
 116     int casos; scanf("%d", &casos); while (casos--) {
 117         for (int p = 0; p < 2; ++p) {
 118             int k; assert(scanf("%d %d %d", &R[p], &V[p], &k) == 3);
 119             P[p].resize(k);
 120             for (int i = 0; i < k; ++i) {
 121                 scanf("%lf %lf %lf", &P[p][i].x, &P[p][i].y, &P[p][i].z);
 122             }
 123             P[p].push_back( point(0, 0, 0) );
 124         }
 125
 126         double totalTime = 1e100;
 127         for (int p = 0; p < 2; ++p) {
 128             double d = 0;
 129             for (int i = 0; i < P[p].size() - 1; ++i) {
 130                 d += dist(P[p][i], P[p][i+1]);
 131             }
 132             totalTime = min(totalTime, d / V[p]);
 133         }
 134         // D(totalTime);
 135         // point p1 = positionAt(0, totalTime);
 136         // point p2 = positionAt(1, totalTime);
 137         // printf("<%lf, %lf, %lf>\n", p1.x, p1.y, p1.z);
 138         // printf("<%lf, %lf, %lf>\n", p2.x, p2.y, p2.z);
 139         vector<double> times;
 140         for (int p = 0; p < 2; ++p) {
 141             double d = 0;
 142             times.push_back(0.0);
 143             for (int i = 0; i < P[p].size() - 1; ++i) {
 144                 d += dist(P[p][i], P[p][i+1]);
 145                 double t = d / V[p];
 146                 if (cmp(t, totalTime) <= 0) times.push_back(d / V[p]);
 147             }
 148         }
 149         sort(times.begin(), times.end());
 150         For(i, 0, times.size() - 1) assert(cmp(times[i], times[i + 1]) <= 0);
 151         times.resize(unique(times.begin(), times.end(), equalWithTolerance) - times.begin());
 152         // for (int i = 0; i < times.size(); ++i) {
 153         //     printf("%lf ", times[i]);
 154         // }
 155         // puts("");
 156
 157         int ans = 0;
 158         for (int i = 0; i < times.size() - 1; ++i) {
 159             //printf("\nInterval from time (%lf, %lf):\n", times[i], times[i+1]);
 160             const double &t = times[i];
 161             if (touchAtTime(t)) {
 162                 //printf("They touch at time %lf, continuing.\n", t);
 163                 continue;
 164             }
 165             double closestTime = findClosestTime(t, times[i+1]);
 166             if (touchAtTime(closestTime)) {
 167                 ans++;
 168             }
 169         }
 170         if (touchAtTime(0.0)) ans++;
 171         printf("%d\n", ans);
 172     }
 173     return 0;
 174 }